COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.COMMENT !XGPCOMMANDS←"/PMAR=2200"
C00004 00003	Scientists often face the difficult
C00017 00004	.GROUP SKIP 2 SELECT 6 INDENT 0,3,0 PREFACE 1 COMPACT
C00025 ENDMK
C⊗;
.COMMENT !XGPCOMMANDS←"/PMAR=2200";
.DEVICE XGP
.FONT 1 "BASL30"
.FONT 2 "BASB30"
.FONT 4  "BASI30"
.FONT 5  "BDR40"
.FONT 6  "NGR25"
.FONT 7  "NGR20"
.FONT A "SUP"
.FONT B "SUB"
.TURN ON "↑α↓_π[]{"
.TURN ON "⊗" FOR "%"
.TURN ON "@" FOR "%"
.PAGE FRAME 54 HIGH 83 WIDE
.AREA TEXT LINES 1 TO 53
.COUNT PAGE PRINTING "1"
.TABBREAK
.ODDLEFTBORDER←EVENLEFTBORDER←1000
.AT "ffi" ⊂ IF THISFONT ≤ 4 THEN "≠"  ELSE "fαfαi" ⊃;
.AT "ffl" ⊂ IF THISFONT ≤ 4 THEN "α∞" ELSE "fαfαl" ⊃;
.AT "ff"  ⊂ IF THISFONT ≤ 4 THEN "≥"  ELSE "fαf" ⊃;
.AT "fi"  ⊂ IF THISFONT ≤ 4 THEN "α≡" ELSE "fαi" ⊃;
.AT "fl"  ⊂ IF THISFONT ≤ 4 THEN "∨"  ELSE "fαl" ⊃;
.SELECT 1
.MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
.MACRO E ⊂ APART END ⊃
.MACRO FAD ⊂ FILL ADJUST DOUBLE SPACE PREFACE 2 ⊃
.MACRO FAS ⊂ FILL ADJUST SINGLE SPACE PREFACE 1 ⊃
.FAS
.COMPACT
.SELECT 1
.PORTION THESIS
.PAGE←0
.NEXT PAGE
.INDENT 0
.TURN OFF "{∞→}"   
.BEGIN CENTER 

⊗5↓_Automated Math Theory Formation_↓⊗*

⊗5Thesis Description⊗*

⊗2Douglas B. Lenat⊗*
Artificial Intelligence Lab
Stanford University
Stanford, California 94305

.END

Scientists often face the difficult
task  of formulating research problems which  must be soluble
yet nontrivial.  In any given branch of science, it is usually easier to tackle a
specific given problem than to  propose interesting yet managable new
questions  to  investigate.   For  example, contrast  ⊗4solving⊗* the
Missionaries and  Cannibals  problem  with the  more  ill-defined
reasoning which led to ⊗4inventing⊗* it.

For my dissertation, I  am investigating creative theory formation in
mathematics: how to  propose interesting new  concepts and  plausible
hypotheses connecting them.  The experimental  vehicle of my research
is   a    computer   program   called   ⊗2AM⊗* (for   ⊗2↓_A_↓⊗*utomated
⊗2↓_M_↓⊗*athematician),   which carries out some of the activities involved
in mathematical research: noticing simple relationships in empirical data,
formulating  new  definitions  out  of  existing  ones,  proposing some
plausible conjectures (and, less importantly, sometimes  proving them),
and evaluating the aesthetic "interestingness" of new concepts.

Before discussing how to ⊗4synthesize⊗* a new theory, consider briefly
how to ⊗4analyze⊗* one, how to construct a plausible chain of
reasoning which terminates in a given discovery. One can do this
by working backwards, by reducing the creative act to simpler and simpler
creative acts.
For  example,
consider  the concept  of prime  numbers.  How might  one  be led  to
define  such a notion? Notice  the following plausible strategy:

.ONCE INDENT 9,9,9
"If f is a function which transforms elements of A into
elements of B, and B is ordered, then consider just those members of A
which are transformed into ⊗4extremal⊗* elements of B.
This  set is an interesting subset of A."

When f(x) means "factors of x", and the ordering is "by length", this
heuristic says to consider  those numbers which have a minimal⊗A1⊗* number
of factors -- that is, the primes. 
So this rule actually ⊗4reduces⊗*  our task from "proposing the concept of
prime numbers" to the more elementary problems of "inventing factorization"
and "discovering cardinality".  

But suppose we know this general rule:
"If  f  is an  interesting  function,  consider its inverse."
It reduces  the task of  discovering factorization  to the  simpler
task  of  discovering multiplication.  
Eventually, this task reduces to the discovery of very basic notions, like
substitution, set-union, and
equality.  To explain how a given researcher might have made a given
discovery, such an analysis is continued until that inductive task is
reduced to "discovering" notions which the researcher already knew.

Suppose a large collection of these  heuristics has been
assembled (e.g., by  analyzing a great many discoveries, and writing down
new heuristic rules whenever  necessary).  
Instead  of using them to ⊗4explain⊗* how a given idea might have
evolved, one can imagine
starting from a basic core of knowledge and
"running"  the
heuristics to ⊗4generate⊗* new concepts.

Such syntheses are precisely what AM does.
The program consists of
a corpus of primitive mathematical concepts and a collection of guiding
heuristics (currently a couple hundred of each).
AM's activities  all serve  to expand AM  itself,⊗A2⊗* to  enlarge upon  a
given body  of mathematical knowledge.  
To cope with  the enormity of
the potential "search space"  involved, 
AM  uses its heuristics as judgmental  criteria to  guide
development  in  the  most  promising   direction.
It appears that  the process of inventing worthwhile new⊗A3⊗* concepts can be guided
successfully using a collection of a few hundred such heuristics.


Each  concept  is represented  as  a ⊗6BEING⊗*⊗A4⊗*, a frame-like data structure 
with  30 different
facets or slots. 
The types of slots include:
⊗6Examples, Definitions,  Generalizations, Utility, Analogies,
Interestingness, Uninterestingness,⊗* and a couple dozen others.
The  ⊗6BEINGs⊗*
representation provides a convenient scheme for organizing the
heuristics; for example, the following strategy
fits into the ⊗4Examples⊗* slot of the
⊗4Predicate⊗* concept:
"If, empirically, 
10 times as many elements ⊗4fail⊗* some predicate P, as ⊗4satisfy⊗* it, then
some ⊗4generalization⊗* (weakened version) of P might be more interesting than P".
AM considers this suggestion after trying to fill in examples of any predicate.⊗A5⊗*


AM is initially  given a large collection of core concepts, with only  a few slots
filled in for each.   Its sole  activity is to  choose some facet  of
some concept,  and fill  in that  particular slot.  In so doing,  new
notions will often  emerge.  Uninteresting ones are forgotten, mildly
interesting ones are kept  as parts of one  slot of one concept,  and
very  interesting ones  are  granted full  concept  status. Such  new
⊗6Beings⊗*  have dozens  of  blank  parts, hence  the  space of
possible actions (slots to fill in) grows rapidly.
The same  heuristics are used both to suggest new directions for
investigation, and to limit attention: both to grow and to prune.


The particular mathematical domains in which AM operates depend  on the choice of
initial concepts. Currently, AM begins with scanty knowledge of a couple 
hundred concepts
which Piaget might describe as ⊗4prenumerical⊗*:
Sets, substitution,  relations, equality, and so on.  In particular,  AM is not
told  anything about  proof,  single-valued functions,
or numbers. 
With this basis, AM quickly discovered elementary numerical concepts
(corresponding to those we refer to as cardinality,
multiplication, factors, and primes)
and wandered around in the domain of elementary number theory.
Although  it  was never able to  ⊗4prove⊗*  the  unique  factorization
theorem, AM actually  did ⊗4conjecture⊗* it.⊗A6⊗*   
"Discovering" a concept means that (1) AM recognized it as a distinguished
entity (e.g., by formulating its definition) and also (2) AM decided it was
worth investigating (either because of the interesting way it was formed, or
because of surprising preliminary empirical results).

AM was not able to discover any "new-to-Mankind" mathematics purely on its own, but
⊗4has⊗* done so when working as a co-researcher with a human.⊗A1⊗*
AM noticed simple new concepts which mathematicians had overlooked, but
AM by itself 
was not able to precisely formulate and prove interesting statements about
those concepts.
I conclude that a synergetic
AM--human combination can sometimes
produce better research than either could alone.

The main difficulty with AM at present is getting it to accurately judge
⊗4a priori⊗* the value of each new concept, to quickly lose interest
in concepts which aren't going to develop into anything.
As with many AI programs, one unexpected aspect of working on AM was the
degree of precision with which one's ideas must be formulated.

Everything that AM does can be viewed as testing the
underlying body of heuristics. Gradually,
this knowledge becomes better organized, its implications clearer.
The resultant body of detailed heuristics may be the germ of a more efficient
programme for educating math students than the current dogma.⊗A7⊗*

But perhaps the most exciting prospect opened up by AM is that
of experimentation: one can vary the concepts AM starts with, vary the
heurisitics available, etc., and study the effects on AM's behavior.
The system 
is just beginning to run well enough  to make such experiments worthwhile.
AM is a dissertation project ⊗4in progress⊗*; few conclusions have been drawn
yet. 

.SKIP TO COLUMN 1

.GROUP SKIP 2 SELECT 6 INDENT 0,3,0 PREFACE 1 COMPACT

********************************************************************************************************

↑1 The other extreme, numbers with a  MAXIMAL number of factors, was
also proposed  by AM as  worth  investigating.    This led AM to  many
interesting questions; the only  "new-to-Mankind" 
mathematical result so far  is that numbers of the following form are
all maximally-divisible:
p⊗B1⊗*⊗Aa1⊗*  p⊗B2⊗*⊗Aa2⊗* p⊗B3⊗*⊗Aa3⊗*...   p⊗Bk⊗*⊗Aak⊗*,  where the
p⊗Bi⊗*'s are the first k consecutive primes, and the exponents a⊗Bi⊗*
decrease   with  i,  and   the  ratio  of   (a⊗Bi⊗*+1)/(a⊗Bj⊗*+1)  is
approximately   (as   closely   as    is   possibe   for    integers)
log(p⊗Bj⊗*)/log(p⊗Bi⊗*). For  example, a typical  divisor-rich number
is
n=2⊗A8⊗*3⊗A5⊗*5⊗A3⊗*7⊗A2⊗*11⊗A2⊗*13⊗A1⊗*17⊗A1⊗*19⊗A1⊗*23⊗A1⊗*29⊗A1⊗*31⊗A1⊗*37⊗A1⊗*41⊗A1⊗*43⊗A1⊗*47⊗A1⊗*53⊗A1⊗*.
The progression of its exponents+1 (9 6 4 3 3 2 2 2 2 2 2 2 2 2 2 2)
is  about as  close  as one  can  get  to satisfying the  "logarithm"
constraint.   This  number n has 3,981,312
divisors. The "AM  Conjecture" is that no  number smaller than n  has
that many divisors. By the way, this n equals 25,608,675,584.
The empirical data gathered indicated the
general character of the declining exponents to AM, but
the precise formulation of the "logs" constraint was beyond AM, since
it doesn't know about logs. In fact, this was the warped way in which
AM first defined a concept like the one we call "logarithm". The proof
of the conjecture involves calculus, and for that reason was also far
beyond the abilities of AM. This example shows the usefulness of a mechanical
"co-researcher",
the effectiveness of AM--human cooperation.

↑2  Incidentally, these  basic concepts  include the  operators which
enlarge the space (e.g., ⊗6COMPOSE-2-RELATIONS⊗* is both a concept in
its own right and a way to generate new ones).
An important kind of heuristic knowledge that AM possesses is how to
create new heuristics to associate with new concepts it defines.
For example, AM has a rule which says that whenever the "looking for
extremals" heuristic is used ("in a situation f:A→B, given an extremal 
b⊗6ε⊗*B,
consider the subset A⊗6'=f⊗*⊗A-1⊗*(b)" ), 
then AM should construct a heuristic like the following and
tack it onto the new concept A':  "A' is a useful space upon which to test
any conjectures involving f or f⊗A-1⊗*". In the case of f="number-of-factors-of",
A and B = Natural numbers, b=2, this rule says to construct the heuristic
"Primes are valuable natural numbers upon which to test conjectures involving
multiplication and factorization". This heuristic is then associated with
the the newly-created Primes concept. So the only heuristics put in by hand
pertain to initially-supplied concepts. All the new heuristics should be
producable from those by AM. In reality, this is not always true; vast
improvements in AM's performance are seen if a human user occasionally
supplies AM with an unperceived heuristic.
Note again the synergetic character of the user--system dialogue.

↑3 Typically, "new" means new to AM, not to Mankind, and "worthwhile"
can only be judged in hindsight.

↑4 Lenat, Douglas, ↓_BEINGS: Knowledge  as Interacting Experts_↓, 4th
IJCAI, 1975, pp. 126-133.

↑5  In fact, after AM  attempts to find examples  of SET-EQUALITY, so
few are  found that  AM  decides to  generalize that  predicate.  The
result is the predicate which means "Has-the-same-length-as" -- i.e.,
the rudiments of Cardinality.

↑6  Due to the firm base of  preliminary concepts which AM developed,
this relationship  was almost obvious.   AM  sought some predicate  P
which,   for  each  n,   some  member  of   FACTORS-OF(n)  satisfied.
ALL-PRIMES was such a  predicate.  AM  next constructed the  relation
which associates,  to each  number n,  all factorizations  of n  into
primes.   The full statement of the UFT  is simply that this relation
is a function; i.e., it is defined and single-valued for  all numbers
n.


↑7 Currently, the educator takes the very best work any mathematician
has  ever done,  polishes it  until its  brilliance is  blinding, and
presents it to the student  to induce upon. 
Many individuals (e.g., Knuth and Polya) have pointed out this blunder.
A few  (e.g.,
Minsky and  Papert at MIT, Adams at  Stanford) are experimenting with
more realistic strategies for "teaching" creativity.